Not Applicable
Not Applicable
All of the material in this patent document is subject to copyright protection under the copyright laws of the United States and of other countries. The owner of the copyright rights has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the United States Patent and Trademark Office file or records, but otherwise reserves all copyright rights whatsoever.
1. Field of the Invention
This invention pertains generally to congestion control systems for communications networks, and more particularly to rate allocation in ATM switched networks.
2. Description of the Background Art
Asynchronous Transfer Mode (ATM) is a networking protocol designed to efficiently support high speed digital voice and data communications. Broadband packet networks based on ATM enable the integration of traffic with a wide range of characteristics within a single communication network. In these networks, all communication at the ATM layer is in terms of fixed-size packets, called xe2x80x9ccellsxe2x80x9d in ATM terminology. An ATM cell consists of 48 bytes of payload and 5 bytes for the ATM-layer header. Routing of cells is accomplished through packet switches over virtual circuits set up between endpoints. By the use of proper traffic scheduling algorithms, ATM is capable of handling multiple classes of traffic ranging from real-time video to best-effort traffic requiring no quality-of-service guarantees. An industry group, the ATM Forum, has defined a family of service categories to address these classes of trafficxe2x80x94specifically: Constant Bit Rate (CBR) service, Variable Bit Rate (VBR) service, Unspecified Bit Rate (UBR) service and Available Bit Rate (ABR) service.
A primary motivation for development of the ABR service category was the economical support of data traffic where each packet of data is segmented into ATM cells. Such xe2x80x9cbest-effortxe2x80x9d traffic is generally characterized as having no real-time deadlines and requiring weak guarantees on the available bandwidth, delay, or cell loss rate. This xe2x80x9cbest-effortxe2x80x9d mode is similar in nature to the service provided by the current Internet (generally using the Transmission Control Protocol (TCP) or User Datagram Protocol (UDP)), except that connections still need to be set up at the ATM layer over virtual circuits between endpoints, either explicitly or implicitly.
ATM raises new opportunities for implementing congestion control at a lower layer, providing the potential for improving the performance of TCP even above that obtained in today""s datagram networks. The higher speed and possibly better congestion control algorithms which may arise with ATM""s ABR service offer promise even for protocols designed for today""s datagram service. The fixed size of ATM cells simplifies the implementation of the switching function in many cases, thus enabling ATM networks to scale up to high speeds.
While a number of congestion-control approaches for best effort traffic in ATM networks have been developed, they exhibit a number of problems including, in many cases, failure to achieve fairness in the allocation of link capacity among competing data flows, complicated buffering and/or queuing schemes, and, in some cases an absence of an end-to-end perspective for the control mechanism. Additionally, most of these approaches require either prior knowledge of the network configuration in order to set correctly the appropriate parameters or cooperation between the high-level protocols and the congestion control mechanisms at the ATM-layer.
One particular congestion control method, explicit rate setting, has been chosen by the ATM Forum as the best match for the ABR service. This method controls the bandwidth allocation to the connections directly. Since each ATM cell contains the same number of bits, control of a connection""s bandwidth, measured as a bit rate, is achieved by directly controlling its cell rate, hence the approach is referred to as rate-based flow control. Control of the cell rate for a connection would occur at least at the transmission source, which would shape the connection""s traffic as directed by feedback from the network. Optionally, such control may occur at points within the network as well. Under a rate-based framework, the share of bandwidth allocated to a connection is not supposed to depend on the delays between points where data is shaped on a per-connection basis.
The rate-based congestion control approach has the potential to provide close-to-ideal throughput with a fraction of the buffering required by link-level flow control, especially for wide area networks. With explicit rate setting, the source of each connection periodically transmits a special resource management (RM) cell. The RM cell specifies the bandwidth requested by the connection. Each switch on the path of the RM cell may modify the request based on the bandwidth it is able to allocate to the connection on its outbound link. On reaching its destination, the RM cell, having had its bandwidth request reduced by any switch unable to allocate the requested bandwidth, is returned to the source, which will then set its rate based on that of the bottleneck link in the path of the connection.
Significantly, however, the rate-based approach requires an algorithm for fair allocation of bandwidth among the connections sharing a common output link of a switch. On receipt of an RM cell from a connection (or, in the general case, a packet containing comparable information), the algorithm is invoked to determine the current bandwidth allocation of the connection on the output link, taking into account the available bandwidth and the current allocations of other connections.
The most robust method for fair rate allocation in packet-switching networks heretofore developed is disclosed in U.S. Pat. No., 5,675,576 to Kalampoukas et al. issued on Oct. 7, 1997, which is incorporated herein by reference. The scheme developed by Kalampoukas et al. addresses rate-based congestion control while still maintaining the max-min fairness criterion. The algorithm described by Kalampoukas et al. requires only a constant number of steps on receipt of an RM cell, in its computation of a fair allocation of the bandwidth for each connection. The algorithm, however, does not support the provision of a minimum guaranteed bandwidth for the connections, but instead treats all the connections equally in distributing the available bandwidth among the set of connections sharing the output link of the switch. Yet, the ability to provide such a guaranteed rate is essential to the support of certain applications, for example, those based on voice or video. In addition, the algorithm described by Kalampoukas et al. requires as an input the total available bandwidth on the output link as a parameter. In practice, however, this parameter may vary from instant to instant and a mechanism is required to estimate it dynamically. Likewise, their method also requires as input the current rate of each connection, typically conveyed within a field in the RM cell, to perform the computations. However, in practice this rate information carried within the RM cell may not correspond to the actual rate of the connection, resulting in inaccuracies in the computations, thus leading to under-utilization or congestion at the output link. Therefore, a means of estimating this actual rate of the connection is essential to avoiding such inaccuracies. Finally, the algorithm described by Kalampoukas et al. does not provide a mechanism for recovering bandwidth from connections that remain idle for a long time, resulting in under-utilization of the bandwidth of the output link.
Therefore, there is a need for a rate-based congestion control scheme that supports a minimum guaranteed rate per connection, has means of estimating the bandwidth of each connection from its actual bandwidth usage, has means for estimating the available bandwidth on the output link, and has an aging mechanism for recovering bandwidth from connections that remain idle for prolonged periods. The present invention satisfies those needs, as well as others, and overcomes the deficiencies of previously developed rate-based congestion control methods.
In general terms, the present invention comprises a congestion control method for communications networks that causes a data source to periodically inject, into a flow of data from that source, a first indicator representative of a rate at which the source is currently transmitting data to the network and a second indicator representative of a rate at which the source is desirous of transmitting data. The invention then determines an allocation according to a predetermined criterion for bandwidth to be apportioned among competing data flows at switches within the network, and operates on the second indicator sent by the source at successive switches in a transmission path in that network between the source and a destination to compare the rate represented by that second indicator with a maximum rate allocation determined by each switch. Where the rate represented by the second indicator is greater than that maximum rate allocation, the invention causes the rate representation in the second indicator to be changed to that maximum rate allocation. After the first and second indicators from the source under consideration have traversed all switches in the network transmission path between that source and the addressed destination, the invention causes those first and second indicators to be returned to the source, whereby any modification of the rate represented by the second indicator by any of the traversed switches operates to establish a maximum data transmission rate for that source.
More particularly, and by way of example and not of limitation, the present invention facilitates its implementation in the switch chipset and enables the algorithm to utilize any unused bandwidth on the outgoing link, thereby improving its responsiveness to changes in available bandwidth. Bandwidth allocations in the algorithm described in U.S. Pat. No. 5,675,576 to Kalampoukas et al. were made based on the requests contained in the CCR (Current Cell Rate) field of the RM cell. However, in practice, the CCR value obtained from the RM cell may not correspond to the actual rate of the connection. The latter may in fact be much lower than the former, resulting in severe under-utilization of the link.
Accordingly, in accordance with an aspect of the present invention, instead of using the value in the CCR field of the RM cell for rate allocation, we estimate the transmission rate of each connection by measuring the interval between the reception of xcex3 RM cells from the given connection. This estimated rate is then used as the requested rate to the rate allocation algorithm. If nj cells from connections; are received during an interval tj in which xcex3 RM cells were received, then the current transmission rate CCRj of the connection is set equal to nj/tj. Note that when the CCRs are computed using this approach, the higher the rates the more frequent the updates. For our simulations, we set the value of xcex3 as 2.
In accordance with another aspect of the invention, in order to add a level of protection against bursty and/or misbehaving sources, the algorithm prechecks if the estimated CCR exceeds the value in the CCR field. In the general case, the minimum of the estimated CCR and the CCR value provided by the RM cell is used as the input to the rate allocation algorithm.
In accordance with still another aspect of the invention, the algorithm takes into account the minimum cell rate (MCR) requirements of ABR connections, still maintaining the max-min fairness when the MCR parameter for each connection is less than its max-min fair allocation. Connections for which the max-min fair rate is less than MCR are called MCR-limited connections. MCR-limited connections are allocated a bandwidth equal to their respective MCRs to satisfy the minimum rate requirement. For the correct operation of the algorithm the number of MCR-limited connections, N., is maintained, as well as the sum of MCRs of MCR-limited connections, denoted as Bl.
In accordance with a further aspect of the invention the algorithm maintains an estimate of the link utilization U and uses this estimate to determine the bandwidth available for ABR traffic, denoted as Ba. If the measured link utilization is greater than one, it is clamped to one. This protects the network from unnecessary oscillations.
Note that, if a rate-allocation algorithm modifies the allocation of a connection only upon receipt of an RM cell from the connection, a connection that remains idle for a long period can maintain its allocation at the switch, potentially causing under-utilization of the link bandwidth. In accordance with still another aspect of the present invention, the solution lies in periodically scanning the allocation table and reducing the allocations for connections that have not transmitted an RM cell within a timeout interval, maintaining only a minimum rate (MCR) for these connections. This scanning algorithm can be run as a background process that is interrupted on receipt of an RM cell, which invokes the rate allocation algorithm. This component of the algorithm has not been used in the simulations, but will be incorporated in the actual implementation.
In accordance with another aspect of the invention, if processing of backward RM cells (BRMs) is possible, the algorithm can be made more responsive to traffic changes in certain network topologies. In this case, the rate allocation of the algorithm is still performed on receipt of forward RM cells, but the ER value in the backward RM cell is marked down to the local allocation computed by the algorithm of the latter is smaller than the former. This improves the responsiveness of the algorithm, particularly when congestion starts to occur.
It is therefore an object of the invention to provide a minimum guaranteed rate for the connections as specified in the Minimum Cell Rate (MCR) field of the RM cell.
Another object of the invention is to provide a rate allocation algorithm having an execution time of order one: "THgr"(1).
Another object of the invention is to provide a rate allocation algorithm that is independent of the number of virtual channels sharing the output link.
Another object of the invention is to provide a rate allocation algorithm that can be implemented in ATM switches carrying a large number of virtual channels.
Another object of the invention is to provide a rate allocation algorithm where, when the total available capacity or the requests of the individual connections change, the algorithm quickly converges to the max-min allocation with a worst-case convergence time of       Θ    ⁢          (              M        ⁢                  (                                    2              ⁢              D                        +                          1              R                                )                    )        ,
where D is the round-trip delay, M is the number of distinct values in the max-min allocation, and R is the rate at which resource-management (RM) cells are transmitted by each source.
Another object of the invention is to provide a rate allocation algorithm that is asynchronous and distributed in nature, does not require cooperation of all the switches in the network, and can be applied in a network with varying link speeds.
Another object of the invention is to provide a rate allocation algorithm that is asynchronous and distributed in nature, attains max-min bandwidth allocations and requires a constant number of simple computations for every RM cell received, thus reducing the asymptotic complexity to "THgr"(1).
Further objects and advantages of the invention will be brought out in the following portions of the specification, wherein the detailed description is for the purpose of fully disclosing preferred embodiments of the invention without placing limitations thereon.